const Dictionary = require("./dictionary");
const Queue = require("./queue");

// BFS breadth first search 广度优先
// DFS depth first search深度优先
class Graph {
  constructor() {
    this.vertexes = []; //存储顶点
    this.adjList = new Dictionary(); // 存储边
  }
  // 添加方法
  addVertex(v) {
    this.vertexes.push(v);
    this.adjList.set(v, []);
  }
  // 添加边
  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }
  // 初始化将节点都设置为白色
  initializeColor() {
    var colors = [];
    for (var i = 0; i < this.vertexes.length; i++) {
      colors[this.vertexes[i]] = "white";
    }
    return colors;
  }
  //   广度优先遍历图结构
  bfs(v, handler) {
    // 1.初始化颜色
    let colors = this.initializeColor();
    // 2.创建队列
    let queue = new Queue();
    // 3.将传入的顶点放入队列中
    queue.enqueue(v);
    // 4.从队列中依次取出和放入数据
    while (!queue.isEmpty()) {
      // 4.1.从队列中取出数据
      let qv = queue.dequeue();
      // 4.2.获取qv相邻的所有顶点
      let qAdj = this.adjList.get(qv);
      // 4.3.将qv的颜色设置成灰色
      colors[qv] = "gray";
      // 4.4.将qAdj的所有顶点依次压入队列中
      for (let i = 0; i < qAdj.length; i++) {
        let a = qAdj[i];
        if (colors[a] === "white") {
          colors[a] = "gray";
          queue.enqueue(a);
        }
      }
      // 4.5.因为qv已经探测完毕, 将qv设置成黑色
      colors[qv] = "black";
      // 4.6.处理qv
      if (handler) {
        handler(qv);
      }
    }
  }
  // 深度优先遍历图结构
  dfs(handler) {
    let colors = this.initializeColor();
    // 2.遍历所有的顶点, 开始访问
    for (var i = 0; i < this.vertexes.length; i++) {
      if (colors[this.vertexes[i]] === "white") {
        this.dfsVisit(this.vertexes[i], colors, handler);
      }
    }
  }
  dfsVisit(u, color, handler) {
    // 1.将u的颜色设置为灰色
    color[u] = "gray";

    // 2.处理u顶点
    if (handler) {
      handler(u);
    }
    // 3.u的所有邻接顶点的访问
    var uAdj = this.adjList.get(u);
    for (var i = 0; i < uAdj.length; i++) {
      var w = uAdj[i];
      if (color[w] === "white") {
        this.dfsVisit(w, color, handler);
      }
    }
    // 4.将u设置为黑色
    color[u] = "black";
  }
  toString() {
    var resultStr = "";
    for (var i = 0; i < this.vertexes.length; i++) {
      resultStr += this.vertexes[i] + "->";
      var adj = this.adjList.get(this.vertexes[i]);
      for (var j = 0; j < adj.length; j++) {
        resultStr += adj[j] + " ";
      }
      resultStr += "\n";
    }
    return resultStr;
  }
}
// 测试代码
var graph = new Graph();

// 添加顶点
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (var i = 0; i < myVertexes.length; i++) {
  graph.addVertex(myVertexes[i]);
}

// 添加边
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");
console.log(graph.toString());
let result = "";
graph.bfs(myVertexes[0], function (v) {
  result += v + " ";
});
console.log(result);
// bfs A B C D E F G H I
// dfs A B E I F C D G H
